package Day11_将字符串翻转到单调递增;

/**
 * ------------------------------------------------------------------------------------------------------
 * 题目：
 *      如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是 单调递增 的。
 *      给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0 。
 *      返回使 s 单调递增的最小翻转次数。
 * ------------------------------------------------------------------------------------------------------
 * 示例：
 *      输入：s = "00110"
 *      输出：1
 *      解释：翻转最后一位得到 00111.
 * ------------------------------------------------------------------------------------------------------
 * 方法：
 *      动态规划
 * ------------------------------------------------------------------------------------------------------
 */
class Solution {
    public static void main(String[] args) {
        String s = "00110";
        System.out.println(minFlipsMonoIncr(s));
    }
    public static int minFlipsMonoIncr(String s) {
        int n = s.length();
        int dp0 = 0, dp1 = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            int dp0New = dp0, dp1New = Math.min(dp0, dp1);
            if (c == '1') {
                dp0New++;
            } else {
                dp1New++;
            }
            dp0 = dp0New;
            dp1 = dp1New;
        }
        return Math.min(dp0, dp1);
    }
}